#include <stdio.h>
#define MaxSize 100
#define N 4
#define M 4
typedef int elem;
typedef struct
{
	int r;
	int c;
	elem d;	
}TupNode;

typedef struct
{
	int row;
	int cols;
	int nums;
	TupNode data[MaxSize];
}TSMatrix;
void CreatMat(TSMatrix &t, elem A[N][M])
{
	int i, j;
	t.row = N;
	t.cols = M;
	t.nums = 0;
	for(i = 0; i < N; i++)
	{
		for(j = 0; j < M; j++)
		{
			if(A[i][j] != 0)
			{
				t.data[t.nums].r = i;
				t.data[t.nums].c = j;
				t.data[t.nums].d = A[i][j];
				t.nums++;
			}
		}
	}
} 
void DipMat(TSMatrix t)
{
	int i;
	if(t.nums <= 0)
		return;
	printf("\t%d\t%d\t%d\n",t.row, t.cols, t.nums);
	printf("-------------------------------------\n");
	for(i = 0; i < t.nums; i++)
		printf("\t%d\t%d\t%d\n",t.data[i].r, t.data[i].c, t.data[i].d);
}
void TranTat(TSMatrix t, TSMatrix &tb)
{
	int p, q = 0, v;
	tb.row = t.cols;
	tb.cols = t.row;
	tb.nums = t.nums;
	if(t.nums != 0)
	{
		for(v = 0; v < t.cols; v++)
		{
			for(p = 0; p < t.nums; p++)
				if(t.data[p].c == v)
				{
					tb.data[q].r = t.data[p].c;
					tb.data[q].c = t.data[p].r;
					tb.data[q].d = t.data[p].d;
					q++;
				}
		}
	}
}
void MatAdd(TSMatrix a, TSMatrix b, TSMatrix &c)
{
	if(a.row != b.row || a.cols != b.cols)
	{
		printf("矩阵相加操作失败\n");
		return;
	}
	c.row = a.row;
	c.cols = a.cols;
	int i = 0 , j = 0, k = 0;
	while(i < a.nums || j < b.nums)
	{
		if(a.data[i].r < b.data[j].r)
		{
			c.data[k].r = a.data[i].r;
			c.data[k].c = a.data[i].c;
			c.data[k].d = a.data[i].d;
			i++;
			k++;
		}
		else if(a.data[i].r == b.data[j].r)
		{
			if(a.data[i].c < b.data[j].c)
			{
				c.data[k].r = a.data[i].r;
				c.data[k].c = a.data[i].c;
				c.data[k].d = a.data[i].d;
				i++;
				k++;
			}
			else if(a.data[i].c == b.data[j].c)
            {
				c.data[k].r = b.data[j].r;
				c.data[k].c = b.data[j].c;
				c.data[k].d = a.data[i].d + b.data[j].d;
				i++;
				j++;
				k++;
			}
			else
			{
				c.data[k].r = b.data[j].r;
				c.data[k].c = b.data[j].c;
				c.data[k].d = b.data[j].d;
				j++;
				k++;
			}
		}
		else
		{
			c.data[k].r = b.data[j].r;
			c.data[k].c = b.data[j].c;
			c.data[k].d = b.data[j].d;
			j++;
			k++;
		}
	}
	c.nums = k;
}
int getvalue(TSMatrix t,int i,int j)
{
	for(int k = 0; k < t.nums; k++)
	{
		if(t.data[k].r == i && t.data[k].c == j)
			return t.data[k].d;
	}
	return 0;
}
void MatMul(TSMatrix a,TSMatrix b,TSMatrix &c)
{
	if(a.cols != b.row)
	{
		printf("矩阵相乘操作失败\n");
		return;
	}
	int i, j, k = 0, s;
	c.row = a.row;
	c.cols = b.cols;
	
	for(i = 0; i < a.row; i++)
	{
		for(j = 0; j < b.cols; j++)
		{
			s = 0;
			for(int m = 0; m < b.cols; m++)
			{
				s = s + getvalue(a, m, i)*getvalue(b, j, m);
			}
			if(s != 0)
			{
				c.data[k].r = i;
				c.data[k].c = j;
				c.data[k].d = s;
				k++;
			}
		}
	}
	c.nums = k;
}

int main()
{
	TSMatrix t1, t2, c;
	elem a[4][4] = {
		{1,0,3,0},
		{0,1,0,0},
		{0,0,1,0},
		{0,0,1,1}};
	CreatMat(t1, a);
	printf("a的三元组:\n");
	DipMat(t1);
	elem b[4][4] = {
		{3,0,0,0},
		{0,4,0,0},
		{0,0,1,0},
		{0,0,0,2}};
	CreatMat(t2, b);
	printf("b的三元组:\n");
	DipMat(t2);
	TranTat(t1, c);
	printf("a转置后\n");
	DipMat(c);
	printf("c = a + b\nc的三元组:\n");
	MatAdd(t1, t2, c);
	DipMat(c);
	printf("c = a * b\nc的三元组:\n");
	MatMul(t1, t2, c);
	DipMat(c);
	return 0;
}